import random
import math
import matplotlib.pyplot as plt  # 导入可视化库

plt.rcParams["font.family"] = ["Microsoft YaHei", "SimHei", "Arial"]
def distance(p1, p2):
    """计算两个点之间的欧氏距离"""
    return math.sqrt(sum((x - y) ** 2 for x, y in zip(p1, p2)))


def assign_cluster(data, centroids):
    """为每个数据点分配最近的簇"""
    clusters = [[] for _ in range(len(centroids))]
    for point in data:
        distances = [distance(point, centroid) for centroid in centroids]
        cluster_idx = distances.index(min(distances))
        clusters[cluster_idx].append(point)
    return clusters


def update_centroids(clusters):
    """更新簇的质心"""
    centroids = []
    for cluster in clusters:
        if cluster:
            centroid = [sum(dim) / len(cluster) for dim in zip(*cluster)]
            centroids.append(centroid)
    return centroids


def Kmeans(data, k, epsilon=1e-4, iteration=100):
    """K均值聚类算法"""
    centroids = random.sample(data, k)
    for i in range(iteration):
        clusters = assign_cluster(data, centroids)
        new_centroids = update_centroids(clusters)
        centroid_change = sum(distance(c, nc) for c, nc in zip(centroids, new_centroids))
        if centroid_change < epsilon:
            break
        centroids = new_centroids
    return clusters, centroids


def plot_clusters(clusters, centroids):
    """可视化聚类结果"""
    # 定义不同簇的颜色和标记
    colors = ['r', 'g', 'b', 'c', 'm', 'y', 'k']  # 支持最多7个簇
    markers = ['o', 's', '^', 'D', 'v', '<', '>']

    plt.figure(figsize=(8, 6))  # 设置图表大小

    for i, cluster in enumerate(clusters):
        # 提取簇中所有点的x和y坐标
        x = [point[0] for point in cluster]
        y = [point[1] for point in cluster]
        # 绘制簇内点（使用不同颜色和标记）
        plt.scatter(x, y, c=colors[i % len(colors)], label=f'簇 {i + 1}',
                    marker=markers[i % len(markers)], alpha=0.6)
        # 绘制质心（用黑色边框突出显示）
        plt.scatter(centroids[i][0], centroids[i][1], c=colors[i % len(colors)],
                    edgecolors='k', s=200, marker='*', label=f'质心 {i + 1}')

    plt.title('K均值聚类结果')
    plt.xlabel('X坐标')
    plt.ylabel('Y坐标')
    plt.legend()  # 显示图例
    plt.grid(alpha=0.3)  # 显示网格
    plt.show()  # 展示图表


if __name__ == "__main__":
    # 生成3组二维数据（模拟3个自然簇）
    data = []
    # 第一组：围绕(0.2, 0.2)分布
    data.extend([[0.2 + random.gauss(0, 0.1), 0.2 + random.gauss(0, 0.1)] for _ in range(30)])
    # 第二组：围绕(0.7, 0.3)分布
    data.extend([[0.7 + random.gauss(0, 0.1), 0.3 + random.gauss(0, 0.1)] for _ in range(30)])
    # 第三组：围绕(0.5, 0.8)分布
    data.extend([[0.5 + random.gauss(0, 0.1), 0.8 + random.gauss(0, 0.1)] for _ in range(30)])

    # 聚类（分成3个簇）
    clusters, centroids = Kmeans(data, k=3)

    # 打印聚类信息
    for i, cluster in enumerate(clusters):
        print(f"簇 {i + 1} 包含 {len(cluster)} 个点，质心为 {[round(x, 3) for x in centroids[i]]}")

    # 可视化结果
    plot_clusters(clusters, centroids)